package com.ujs.listnode.code.intersectionNode;

import com.ujs.listnode.code.ListNode;

/**
 * @author zhangshihao
 * @create 2023-10-11 20:45
 * <p>
 * 面试题 02.07. 链表相交
 * https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
 */
public class IntersectionNode {
    public static void main(String[] args) {
        ListNode headA = new ListNode(4);
        ListNode node1A = new ListNode(1);
        ListNode node2 = new ListNode(8);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(5);
        headA.next = node1A;
        node1A.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(null);

        ListNode headB = new ListNode(5);
        ListNode node1B = new ListNode(0);
        ListNode node2B = new ListNode(1);
        headB.next = node1B;
        node1B.next = node2B;
        node2B.next = node2;
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(null);
        ListNode intersectionNode = getIntersectionNode2(headA, headB);
        // System.out.println(nodeListLength(headA));
        // System.out.println(nodeListLength(headB));
        System.out.println(intersectionNode.val);
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != null) {
            while (curB != null) {
                if (curA == curB) {
                    return curB;
                }
                curB = curB.next;
            }
            curB = headB;
            curA = curA.next;
        }
        return null;
    }

    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        int nodeALength = nodeListLength(headA);
        int nodeBLength = nodeListLength(headB);
        ListNode curA = headA;
        ListNode curB = headB;
        if (nodeALength > nodeBLength) {
            // 将A的指针向后移动到和B相同长度的位置
            for (int i = 0; i < nodeALength - nodeBLength; i++) {
                curA = curA.next;
            }
        } else {
            // 将B的指针向后移动到和A相同长度的位置
            for (int i = 0; i < nodeBLength - nodeALength; i++) {
                curB = curB.next;
            }
        }
        // 开始比较是否相等
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

    public static int nodeListLength(ListNode head) {
        ListNode cur = head;
        int length = 0;
        while (cur != null) {
            cur = cur.next;
            length++;
        }
        return length;
    }
}
